//Given two arrays nums1 and nums2 of equal size, the advantage of nums1 with re
//spect to nums2 is the number of indices i for which nums1[i] > nums2[i]. 
//
// Return any permutation of nums1 that maximizes its advantage with respect to 
//nums2. 
//
// 
//
// 
// Example 1: 
//
// 
//Input: nums1 = [2,7,11,15], nums2 = [1,10,4,11]
//Output: [2,11,7,15]
// 
//
// 
// Example 2: 
//
// 
//Input: nums1 = [12,24,8,32], nums2 = [13,25,32,11]
//Output: [24,32,8,12]
// 
//
// 
//
// Note: 
//
// 
// 1 <= nums1.length = nums2.length <= 10000 
// 0 <= nums1[i] <= 109 
// 0 <= nums2[i] <= 109 
// 
// 
// 
// Related Topics 贪心算法 数组 
// 👍 127 👎 0


package leetcode.editor.cn;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

//Java：Advantage Shuffle
class P870AdvantageShuffle {
    public static void main(String[] args) {
        Solution solution = new P870AdvantageShuffle().new Solution();
        // TO TEST
        solution.advantageCount(new int[]{12, 24, 8, 32}, new int[]{13, 25, 32, 11});
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[] advantageCount(int[] nums1, int[] nums2) {
            PriorityQueue<int[]> maxQueue = new PriorityQueue<>(new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    return o2[1] - o1[1];
                }
            });
            for (int i = 0; i < nums2.length; i++) {
                maxQueue.offer(new int[]{i, nums2[i]});
            }
            Arrays.sort(nums1);
            int left = 0, right = nums1.length - 1;
            int[] result = new int[nums1.length];
            while (maxQueue.isEmpty() != true) {
                int[] nums2Arr = maxQueue.poll();
                if (nums2Arr[1] < nums1[right]) {
                    result[nums2Arr[0]] = nums1[right--];
                }else{
                    result[nums2Arr[0]] = nums1[left++];
                }
            }
            return result;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}